package week02

// 410. 分割数组的最大值
// https://leetcode-cn.com/problems/split-array-largest-sum/

func splitArray(nums []int, m int) int {
	var left, right = 0, 0
	for _, num := range nums {
		left = max(left, num) // 每个数字分一组，和的最大值就是数组中的最大值
		right += num    // 上限是所有数字都分一组
	}
	for left < right {
		var mid = (right - left) / 2 + left
		if isValid(nums, m, mid) {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return right
}

func isValid(nums []int, m int, target int) bool {
	var sum = 0
	var group = 1
	for _, num := range nums {
		if sum+num <= target {
			sum += num
		} else {
			group++
			sum = num
		}
	}
	return group <= m
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
